

#include"stl_heap.h"

#include<stdlib.h>

/// <summary>
/// 分配堆的内存
/// </summary>
/// <param name="heap">堆</param>
/// <param name="capacity">堆的数组容量,实际容量是capacity-1</param>
/// <param name="is_MaxHeap">是否大根堆</param>
/// <param name="c">比较函数(key1,key2):key1大于key2返回1,key1小于key2返回-1,key1等于key2返回0</param>
void Heap_allocate(Heap* heap, int capacity, bool is_MaxHeap, int (*c)(Datapointer, Datapointer)) {
	heap->data_buffer = (Datapointer*)malloc(capacity * sizeof(Datapointer));
	heap->count = 0;
	heap->Capacity = capacity;
	heap->is_MaxHeap = is_MaxHeap;
	heap->match = c;
}

/// <summary>
/// 释放堆的内存。
/// </summary>
/// <param name="heap"></param>
void Heap_deallocate(Heap* heap) {
	free(heap->data_buffer);
	heap->count = 0;
	heap->Capacity = 0;
	heap->is_MaxHeap = true;
	heap->match = NULL;
}

/// <summary>
/// 大根堆调整
/// 对heap的索引为k的子树进行调整。
/// </summary>
/// <param name="A">堆的数组heap->data_buffer(从1开始索引)</param>
/// <param name="k">需要调节的子树的根节点索引</param>
/// <param name="len">堆的节点数量heap->count</param>
/// <param name="c">比较函数(key1,key2):key1大于key2返回1,key1小于key2返回-1,key1等于key2返回0</param>
void MaxHeap_adjust(Datapointer* A, int k, int len, int (*c)(Datapointer, Datapointer)) {
	//int len = heap->count;
	//Datapointer* A = heap->data_buffer;
	
	A[0] = A[k];   // A[0]缓存子树根节点
	for (int i = k << 1; i <= len; i = i << 1) {
		if (i < len && c(A[i], A[i + 1]) == -1)
			//if (i < len && A[i] < A[i + 1])
		{  //沿较大的子节点向下筛选
			i++;               // 这里i 是较大的子节点。
		}

		if (c(A[0], A[i]) >= 0)break; // 不需要调整根节点，直接退出循环。
		//if (A[0] >= A[i])break; // 不需要调整根节点，直接退出循环。
		else
		{
			A[k] = A[i];  // 将大的节点调整到双亲(子树根)上
			k = i;        // 调整子树根，以便继续向下筛选（一旦根有调整，就要调整子树）。
		}
	}
	A[k] = A[0];  // 被筛出来的节点放入最后的位置。
}

/// <summary>
/// 小根堆调整
/// 对heap的索引为k的子树进行调整。
/// </summary>
/// <param name="A">堆的数组heap->data_buffer(从1开始索引)</param>
/// <param name="k">需要调节的子树的根节点索引</param>
/// <param name="len">堆的节点数量heap->count</param>
/// <param name="c">比较函数(key1,key2):key1大于key2返回1,key1小于key2返回-1,key1等于key2返回0</param>
void MinHeap_adjust(Datapointer* A, int k, int len, int (*c)(Datapointer, Datapointer)) {
	//int len = heap->count;
	//Datapointer* A = heap->data_buffer;

	A[0] = A[k];   // A[0]缓存子树根节点
	for (int i = k << 1; i <= len; i = i << 1) {
		if (i < len && c(A[i], A[i + 1]) == 1)   //沿较小的子节点向下筛选
			//if (i < len && A[i] > A[i + 1]) 
		{  //沿较小的子节点向下筛选
			i++;               // 这里i 是较小的子节点。
		}

		if (c(A[0], A[i]) <= 0)break; // 不需要调整根节点，直接退出循环。
		//if (A[0] <= A[i])break; // 不需要调整根节点，直接退出循环。
		else
		{
			A[k] = A[i];  // 将小的节点调整到双亲(子树根)上
			k = i;        // 调整子树根，以便继续向下筛选（一旦根有调整，就要调整子树）。
		}
	}
	A[k] = A[0];  // 被筛出来的节点放入最后的位置。
}

/// <summary>
/// 将链表的元素Datapointer构建成堆。
/// </summary>
/// <param name="heap">堆</param>
/// <param name="list">链表</param>
void Heap_build_with_list(Heap* heap, List* list) {
	int count = list->count;
	if (count >= heap->Capacity) {  // 限制容量
		count = heap->Capacity - 1;
	}
	heap->count = count;
	//取链表前面count 个元素。
	ListNode* cursor = list->tail;
	for (int i = 1; i <= count; i++) {
		cursor = cursor->next;
		heap->data_buffer[i] = cursor->datap;
	}

	// 构建堆
	Datapointer* A = heap->data_buffer;
	/// 比较函数（key1,key2）: key1 > key2返回1，key1 < key2返回-1,key1 = key2返回0.
	int (*match)(Datapointer key1, Datapointer key2) = heap->match;
	if (heap->is_MaxHeap) {
		for (int i = count / 2; i > 0; i--) {
			MaxHeap_adjust(A, i, count, match);
		}
	}
	else
	{
		for (int i = count / 2; i > 0; i--) {
			MinHeap_adjust(A, i, count, match);
		}
	}
}

/// <summary>
/// 将数组的元素构建成堆。
/// </summary>
/// <param name="heap">堆</param>
/// <param name="dat">数据数组</param>
/// <param name="dat_len">数组长度</param>
void Heap_build_with_array(Heap* heap, Datapointer* dat,int dat_len) 
{
	int count = dat_len;
	if (count >= heap->Capacity) {  // 限制容量
		count = heap->Capacity - 1;
	}
	heap->count = count;
	//取链表前面 count 个元素。
	for (int i = 1; i <= count; i++) {
		heap->data_buffer[i] = dat[i - 1];
	}

	

	// 构建堆
	Datapointer* A = heap->data_buffer;
	/// 比较函数（key1,key2）: key1 > key2返回1，key1 < key2返回-1,key1 = key2返回0.
	int (*match)(Datapointer key1, Datapointer key2) = heap->match;
	if (heap->is_MaxHeap) {
		for (int i = count / 2; i > 0; i--) {
			MaxHeap_adjust(A, i, count, match);
		}
	}
	else
	{
		for (int i = count / 2; i > 0; i--) {
			MinHeap_adjust(A, i, count, match);
		}
	}
}

/// <summary>
/// 堆排序，堆排序后，现有的堆会倒转，原来的大根堆会变成小根堆，小根堆变成大根堆。
/// 时间复杂度：O(n*Log(n))
/// 如果原来是大根堆，排序后是从小到大，大根堆变成小根堆。
/// 如果原来是小根堆，排序后是从大到小，小根堆变成大根堆。
/// </summary>
/// <param name="heap"></param>
void Heap_sort(Heap* heap)
{
	int len = heap->count;
	Datapointer* A = heap->data_buffer;
	Datapointer t;
	/// 比较函数（key1,key2）: key1 > key2返回1，key1 < key2返回-1,key1 = key2返回0.
	int (*match)(Datapointer key1, Datapointer key2) = heap->match;

	if (heap->is_MaxHeap) {
		for (int i = len; i > 1; i--) {	
			t = A[1];
			A[1] = A[i];
			A[i] = t;		// 推出堆顶元素，和堆底交换
			MaxHeap_adjust(A, 1, i - 1, match);
		}
		heap->is_MaxHeap = false;
	}
	else
	{
		for (int i = len; i > 1; i--) {
			t = A[1];
			A[1] = A[i];
			A[i] = t;		// 推出堆顶元素，和堆底交换
			MinHeap_adjust(A, 1, i - 1, match);
		}
		heap->is_MaxHeap = true;
	}
}


/// <summary>
/// 往堆中推入一个元素，时间复杂度：Log(n)
/// </summary>
/// <param name="heap">堆</param>
/// <param name="datap">数据指针</param>
/// <returns>true: 成功插入；false：插入失败，堆已满</returns>
bool Heap_push(Heap* heap,Datapointer datap)
{
	Datapointer* A = heap->data_buffer;
	if (heap->count < heap->Capacity - 1) {
		heap->count++;
		int k = heap->count;
		int hk = k >> 1;

		if (heap->is_MaxHeap) {
			while (k > 1)  // 不是根节点
			{
				if (heap->match(datap, A[hk]) == 1) {
					A[k] = A[hk];
					k = hk;
					hk = hk >> 1;
				}
				else
					break;
			}
			A[k] = datap;
		}
		else {
			while (k > 1)  // 不是根节点
			{
				if (heap->match(datap, A[hk]) == -1) {
					A[k] = A[hk];
					k = hk;
					hk = hk >> 1;
				}
				else
					break;
			}
			A[k] = datap;
		}

		return true;
	}
	return false;
}

/// <summary>
/// 弹出堆顶元素，时间复杂度：Log(n)
/// </summary>
/// <param name="heap"></param>
/// <returns>堆顶元素。NULL：弹出失败，堆已空</returns>
Datapointer Heap_pop(Heap* heap) {
	Datapointer* A = heap->data_buffer;
	if (heap->count > 0) {
		Datapointer top = A[1];
		A[1] = A[heap->count];
		heap->count--;
		if (heap->is_MaxHeap)
			MaxHeap_adjust(A, 1, heap->count, heap->match);
		else
			MinHeap_adjust(A, 1, heap->count, heap->match);

		return top;
	}
	return NULL;
}


/////////////////////////////////////////////////////////////////

int matchi(Datapointer key1, Datapointer key2)  //key1>key2返回1，key1<key2返回-1,key1=key2返回0.
{
	if (*(int*)key1 > *(int*)key2)return 1;
	else if (*(int*)key1 < *(int*)key2)return -1;
	else return 0;
}


void print_int_heap(Heap heap)
{
	printfs("  heap count: %d  :::: ", heap.count);
	for (int i = 1; i <= heap.count; i++) {
		printfs(" %d, ", *(int*)heap.data_buffer[i]);
	}
	printfs("  \r\n");
}

void test_heap()
{
//	int a[] = { 15,9,7,8,20,-1,7,4 };
	int a[] = { 23,17,72,60,25,8,68,71,52 };

	int len = sizeof(a) / sizeof(int);
	Datapointer dat[30];

	Heap heap;
	Heap_allocate(&heap, len, true, matchi);
	
	for (int i = 0; i <= len; i++) {
		Heap_push(&heap, a + i);
		print_int_heap(heap);
		dat[i] = a + i;
	}
	print_int_heap(heap);

	Heap_deallocate(&heap);
	Heap_allocate(&heap, len, false, matchi);


	Heap_build_with_array(&heap, dat, len);
	print_int_heap(heap);

	printfs(" \r\n");
	Heap_sort(&heap);
	print_int_heap(heap);
	printfs(" \r\n");
	Heap_sort(&heap);
	print_int_heap(heap);
	printfs(" \r\n");


	for (int i = 0; i <= len; i++) {
		Heap_pop(&heap);
		print_int_heap(heap);
	}


	printfs(" \r\n test heap %d .", len);

	Heap_deallocate(&heap);
}





